#include <bits/stdc++.h>

constexpr int P = 10'007;

void inc(int &x, const int y) {
    x += y;
    if (x >= P) x -= P;
}

constexpr int N = 1'000;

int d[N];
int inv[N + 1];
int f[N + 1][N + 1];

int c2(int x) {
    return x * (x - 1) / 2 % P;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, k;
    std::cin >> n >> m >> k;
    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;
        --u;
        --v;
        d[u] ^= 1;
        d[v] ^= 1;
    }
    inv[0] = 1;
    inv[1] = 1;
    for (int i = 2; i <= k; ++i) inv[i] = (P - P / i) * inv[P % i] % P;

    f[0][std::accumulate(d, d + n, 0)] = 1;
    for (int i = 1; i <= k; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (j + 2 <= n) {
                inc(f[i][j], f[i - 1][j + 2] * c2(j + 2) % P);
            }
            if (j >= 1 && n - j >= 1) {
                inc(f[i][j], f[i - 1][j] * j % P * (n - j) % P);
            }
            if (j >= 2) {
                inc(f[i][j], f[i - 1][j - 2] * c2(n - j + 2) % P);
            }
            if (i >= 2) {
                inc(f[i][j], P - f[i - 2][j] * (c2(n) - (i - 2) + P) % P);
            }
            f[i][j] = 1ll * f[i][j] * inv[i] % P;
        }
    }
    std::cout << f[k][0] << '\n';

    return 0;
}